package algorithm7.leetcode.每日一题.YEAR2023.month5;

import org.junit.jupiter.api.Test;

import java.math.BigDecimal;
import java.util.HashSet;
import java.util.Set;

public class DAY20230510_LC1015 {

/*
给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。
返回 n 的长度。如果不存在这样的 n ，就返回-1。
注意： n 不符合 64 位带符号整数。

提示：
1 <= k <= 10^5


示例 1：
输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。
 */

    public int smallestRepunitDivByK(int k) {
//        return handle1(k);
//        return handle2(k);
        return handle3(k);
    }

    private int handle3(int k) {
        long xxx = 0;
        Set<Long> set = new HashSet<>();
        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            xxx = xxx * 10 + 1;
            long remainder = xxx % k;
            if (set.contains(remainder)) {
                return -1;
            }
            if (remainder == 0) {
                return (int) ++i;
            }
            set.add(remainder);
        }
        return -1;
    }

    private int handle2(int k) {

        int p = 0;
        for (int i = 1; i <= k; i++) {
            p = (p * 10 + 1) % k;
            if (p == 0) {
                return i;
            }
        }
        return -1;
    }

    private int handle1(int k) {
        BigDecimal t;
        BigDecimal bk = new BigDecimal(k);
        StringBuilder sb = new StringBuilder();
        do {
            t = new BigDecimal(sb.append("1").toString());
            BigDecimal[] x = t.divideAndRemainder(bk);
            if (x[1].equals(BigDecimal.ZERO)) {
                return String.valueOf(t).length();
            }
        } while (t.toString().length() <= 20);
        return -1;
    }

    @Test
    void t1() {
        BigDecimal bigDecimal = new BigDecimal("111111111111111");
        BigDecimal[] bigDecimals = bigDecimal.divideAndRemainder(new BigDecimal("17"));
        System.out.println("bigDecimals = " + bigDecimals[1].toString());
        System.out.println("bigDecimals = " + bigDecimals[0].toString());
        int k = 17;
        int res = smallestRepunitDivByK(k);
        System.out.println("res = " + res);
    }
}
